/*********************************************************************************
 *      Copyright:  (C) 2017 luminqi
 *                  All rights reserved.
 *
 *       Filename:  binary_search.c
 *    Description:  This file 
 *                 
 *        Version:  1.0.0(2017年08月26日)
 *         Author:  luminqi <958822582@qq.com>
 *      ChangeLog:  1, Release initial version on "2017年08月26日 13时39分07秒"
 *                 
 ********************************************************************************/

#include <stdio.h>

int binary_search(int array[], int low, int high, int key);
int main(int argc, char **argv)
{
    int n = 0;
    int i = 0;
    printf("the array has n number:");
    scanf("%d",&n);
    int a[n];

    printf("please input n orderer number:\n");
    for (i = 0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }

    int res = 0;
    int key = 0;

    printf("please input a key:\n");
    scanf("%d",&key);
    res = binary_search(a, 0, n-1, key);
    if (res == -1)
    {
        printf("not found!");
    }
    else
    {
        printf("the index of %d is array[%d]\n",key,res);
    }
    return 0;
}

int binary_search(int array[], int low, int high, int key)
{
    int i = low;
    int j = high;
    int mid = 0;

    if (low<=high)
    {
        mid = i + (j-i)/2;
        if (array[mid]==key)
        {
            return mid;
        }
        if (array[mid]>key)
        {
            return binary_search(array,i,mid-1,key);
        }
        else
        {
            return binary_search(array,mid+1,j,key);
        }
    }
    else
    {
        return -1;
    }
}
